package ahaArithmetic;

public class Sort {

    //木桶排序
    public static void cannikin(int[] numbers,int n){
        Long time = System.currentTimeMillis();
        //创建n+1个木桶
        int[] result = new int[n+1];
        //初始值为0
        for(int i=0;i<=n;i++){
            result[i] = 0;
        }
        //给木桶赋值
        for(int left=0;left<numbers.length;left++){
            if(numbers[left]!=0){
                result[numbers[left]]++;
            }
        }
        //输出值
        /*for(int k=n;k>0;k--){
            for(int x=result[k];x>0;x--){
                System.out.println(k);
            }
        }*/
        Long time2 = System.currentTimeMillis();
        System.out.println(time2-time);
    }

    //冒泡排序
    public static void bubbling(int[] numbers){
        int a=0;
        for(int k=numbers.length-1;k>=1;k--){
            for(int left=0;left<k;left++){
                if(numbers[left]<numbers[left+1]){
                    a=numbers[left];
                    numbers[left]=numbers[left+1];
                    numbers[left+1]=a;
                }
            }
        }
        //print(numbers);
    }

    /*快速排序(辣鸡实现)
    * 效率比冒泡高,且没有递归代码，没有栈溢出情况*/
    public static void fast(int[] numbers){
        int left=0,k=numbers.length-1;
        int basic = 0;
        int c =0;
        for(;basic<numbers.length-1;basic++,left=basic,k=numbers.length-1) {
            while (!(left == basic && k == basic)) {
                while (true) {
                    while (numbers[k] >= numbers[basic] && left != k) {
                        k--;
                        //System.out.println("k=" + k + " " + "left=" + left);
                    }
                    while (numbers[left] <= numbers[basic] && k != left) {
                        left++;
                        //System.out.println("k=" + k + " " + "left=" + left);
                    }
                    if (left == k) {
                        c = numbers[left];
                        numbers[left] = numbers[basic];
                        numbers[basic] = c;
                        //print(numbers);
                        left = basic;
                        break;
                    } else {
                        c = numbers[left];
                        numbers[left] = numbers[k];
                        numbers[k] = c;
                        //print(numbers);
                    }
                }
            }
        }
        //print(numbers);
    }

    //快速排序（标准实现）
    public static void fastPlus(int[] numbers,int left,int right){
        int c,basic=left;
        while (left != right) {
            while (numbers[right] >= numbers[basic] && left != right) {
                right--;
                //System.out.println("right=" + right + " " + "left=" + left);
            }
            while (numbers[left] <= numbers[basic] && right != left) {
                left++;
                //System.out.println("right=" + right + " " + "left=" + left);
            }
            if (left == right) {
                c = numbers[left];
                numbers[left] = numbers[basic];
                numbers[basic] = c;
                //print(numbers);
                break;
            } else {
                c = numbers[left];
                numbers[left] = numbers[right];
                numbers[right] = c;
                //print(numbers);
            }
        }
        if(left==0&&right==0 || left==numbers.length-1&&left==right){
            return;
        }
        //递归左边
        fastPlus(numbers,0,left-1);
        //递归右边
        fastPlus(numbers,right+1,numbers.length-1);
        //print(numbers);
    }


    private static void print(int[] numbers){
        for (int x:numbers) {
            System.out.print(x+" ");
        }
        System.out.println();
    }
}
